void GetNext(int* Next, char* str)
{
    int len = strlen(str);
    Next[0] = -1;
    int k = -1;
    int j = 0;
    int i = j + 1;
    while (i < len)
    {
        if (k == -1 || str[i - 1] == str[k])
        {
            Next[i] = k + 1;
            i++;
            k++;
        }
        else
            k = Next[k];
    }
}
int strStr(char* haystack, char* needle) {
    int len_hay = strlen(haystack);
    int len_need = strlen(needle);
    int i = 0, j = 0;
    if (len_need > len_hay)
        return -1;
    if (len_hay == 0 && len_need == 0)
        return 0;
    int* Next = (int*)malloc(sizeof(int) * len_need);
    GetNext(Next, needle);
    while (i < len_hay && j < len_need)
    {
        if (haystack[i] == needle[j])
        {
            i++;
            j++;
        }
        else if (j != 0)
            j = Next[j];
        else
            i++;
    }
    if (j >= len_need)
        return i - j;
    return -1;
}